import java.util.Stack;

/**
 * Created by L.jp
 * Description:给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 * User: 86189
 * Date: 2023-03-17
 * Time: 1:25
 */
public class Solution {
    public boolean isValid(String s) {
        //遇到左括号入栈，遇到右括号弹出左括号再匹配
        /*Stack<Character> stack=new Stack<>();
        for(int i = 0; i <s.length(); i++){
            char c=s.charAt(i);
            if(c =='(' ||c == '{' || c=='['){
                stack.push(s.charAt(i));
            }else{
                if(stack.size()==0){
                    return false; //如果第一次遍历之后stack为0说明，第一个为右括号，不可能匹配成功，返回false
                }
                Character cp=stack.pop();
                if(cp=='(' && c!=')'){
                    return false;
                }
                if(cp=='{' && c!='}'){
                    return false;
                }
                if(cp=='[' && c!=']'){
                    return false;
                }
            }
        }
        return stack.size()==0;*/
        
        //优化，遇到左括号，让其对应的右括号入栈，遇到右括号就弹出栈顶元素，看两个元素是否匹配
        Stack<Character> stack=new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(c=='(') stack.push( ')' );
            else if(c=='{') stack.push( '}' );
            else if(c=='[') stack.push( ']' );
            else if(stack.isEmpty() || stack.peek()!=c) return false; //第一个为右括号或者最近一次入栈的右括号跟当前右括号不匹配，返回false
            else stack.pop(); //如果两个右括号匹配，那么说明上一个左括号和下一个右括号是匹配的
         }
         return stack.isEmpty();
    }
}
